"""
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

153. 寻找旋转排序数组中的最小值
已解答
中等
相关标签
相关企业
提示
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
 

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

"""

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        """
        左右指针按照左包右包原则
        分别从left=0和right=n-1开始比较，
        如果nums[left]<nums[right]，则说明该数组正常，最小值即为nums[left]
        否则如果nums[left]>nums[right]，说明该范围内必定有最小值，通过获取mid进行测试：
        其中必定有nums[left]>nums[mid]或nums[mid]>nums[right]。（否则nums[left]<nums[mid]<nums[right]与原假设矛盾）
        考虑下二者同时出现的可能：不可能。原来的数组无论旋转多少次，只能保证至多出现一对相邻的数字，使前者大于后者。
        换言之，矛盾的range至多只可能有一片，利用此特性不断缩减range，最后使得left+1==right
        则最小值就是nums[right]
        """
        left=0
        right=len(nums)-1
        if nums[left]<nums[right]:
            return nums[left]
        while left+1<right:
            mid=(left+right)//2
            if nums[left]>nums[mid]:
                right=mid
            else:
                left=mid
            
        return nums[right]

        pass


if __name__=='__main__':

    s=Solution()
    nums=[11,13,15,17]
    res=s.findMin(nums)
    print(res)

    pass
